package 动态规划.另类的;

import org.junit.Test;
import 差分Plus离散化.美团流星差分solution;

import java.util.Arrays;
import java.util.TreeSet;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/9/10 14:28
 */
public class b站笔试 {
    /*
        给你一个由正整数组成的数组nums 和一个正整数k，找出数组nums中所有符合以下条件的非空子集，返回子集数量。
        条件:在nums子集中，任意两个整数的绝对差值均不等于k。
        1 <= nums.length <= 25
        1 <= nums[i],k <= 500
        nums子集定义:可以经由nums删除某些元素(也可能不删除)得到的一个数组。只有在“删除元素时，选择的数组索引不同”的情况下，两个子集才会被视作是不同的子集,
     */

    public static void main(String[] args) {
        int nums[] = {2,4,6} , k = 2;
        System.out.println(solve(nums,k));
    }

    public static int solve(int nums[],int k){
        Arrays.sort(nums);

        return recursion(nums,0,new boolean[10],k) - 1; // 减的 是  空集 把空集给减掉
    }
    public static int recursion(int nums[],int index,boolean vis[],int k){
        if(index == nums.length ){
//            System.out.println(Arrays.toString(vis));
            return 1;
        }
        // 子集型问题, 选或者不选
        // 不选
        int ans = recursion(nums,index + 1,vis,k);
        // choose 但是 有决策限制
        if(nums[index] > k && vis[nums[index] - k]){
            // 因为 nums 是排好序的, 并且都是整数 ,nums[index] > k , 为了防止 vis[] 数组 下标越界
            return ans;
        }
        vis[nums[index]] = true; // 选上的标志
        ans += recursion(nums,index + 1,vis,k);
        vis[nums[index]] = false; // backTracing
        return ans;
    }




    /*
        给你一个下标从0开始的整数数组nums。nums 的-个子数组如果满足以下条件，那么它是 不间断的:
i，i+1，...，j 表示子数组中的下标。对于所有满足i<=i1,i2 <=j的下标对，都有0<=|nums[i1]- nums[i2]| <= 2
请你返回 不间断子数组的总数目。子数组是一个数组中一段连续非空的元素序列
1 <= nums.length <= 10^4
     */
    //暴力解 O(n ^ 2)
    // 但是感觉 是能 A掉这个题, 可能吧
    public int solve(int nums[]){
        // 不能排序, 子数组, 下标位置 是有关系的
        int ans = 0;
        for (int i = 0; i < nums.length; i++) {
            int max = nums[i], min = nums[i];
            for (int j = i; j < nums.length; j++) {
                max = Math.max(max,nums[j]);
                min = Math.min(min,nums[j]);
                if(max - min > 2 || max - min < 0){
                    break;
                }
                ans++;
            }
        }
        return ans;
    }


    /*
     正确解法
     本题是一个好题，主要考察 有序集合 和 贡献度思想：可以采用 multiset 保存遍历的所有元素（遍历右端点），
     如果出现最大元素-最小元素大于2的情况，那么就收缩左边界；
     同时累加 以i为右端点的数组数目；当然其他解法，例如单调队列等，也可以自己做做尝试；
     */
    public int subArrNum(int[] arr) {
        int n = arr.length;
        int ans = 0;
        TreeSet<Integer> set = new TreeSet<>();
        for (int i = 0, l = 0; i < n; ++i) {
            set.add(arr[i]);
            while (set.last() - set.first() > 2) {
                set.remove(arr[l]);
                l++;
            }
            ans += i - l + 1;
        }
        return ans;
    }




    @Test
    public void test(){
        int nums[] = {3,2,1};
        int solve = solve(nums);
        System.out.println(solve);
//        int i = countNonOverlappingSubarrays(nums);
//        System.out.println(i);
    }
}
